home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / ddj0492.zip / DFLT11.ZIP / HTREE.C < prev    next >
Text File  |  1992-01-06  |  1KB  |  55 lines
  1. /* ------------------- htree.c -------------------- */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include "htree.h"
  6.  
  7. struct htree *ht;
  8. int root;
  9.  
  10. /* ------ build a Huffman tree from a frequency array ------ */
  11. void buildtree(void)
  12. {
  13.     int treect = 256;
  14.     int i;
  15.  
  16.     for (i = 0; i < treect; i++)    {
  17.         ht[i].parent = -1;
  18.         ht[i].right  = -1;
  19.         ht[i].left   = -1;
  20.     }
  21.     /* ---- build the huffman tree ----- */
  22.     while (1)   {
  23.         int h1 = -1, h2 = -1;
  24.         /* ---- find the two smallest frequencies ---- */
  25.         for (i = 0; i < treect; i++)   {
  26.             if (i != h1) {
  27.                 struct htree *htt = ht+i;
  28.                 if (htt->cnt > 0 && htt->parent == -1)   {
  29.                     if (h1 == -1 || htt->cnt < ht[h1].cnt) {
  30.                         if (h2 == -1 || ht[h1].cnt < ht[h2].cnt)
  31.                             h2 = h1;
  32.                         h1 = i;
  33.                     }
  34.                     else if (h2 == -1 || htt->cnt < ht[h2].cnt)
  35.                         h2 = i;
  36.                 }
  37.             }
  38.         }
  39.         if (h2 == -1) {
  40.             root = h1;
  41.             break;
  42.         }
  43.         /* --- combine two nodes and add one --- */
  44.         ht[h1].parent = treect;
  45.         ht[h2].parent = treect;
  46.         ht = realloc(ht, (treect+1) * sizeof(struct htree));
  47.         ht[treect].cnt = ht[h1].cnt + ht[h2].cnt;
  48.         ht[treect].right = h1;
  49.         ht[treect].left = h2;
  50.         ht[treect].parent = -1;
  51.         treect++;
  52.     }
  53. }
  54.  
  55.